The present invention relates generally to the field of ad-hoc network optimization. More particularly, the present invention relates to systems and methods for efficiently allocating bandwidth utilizing a connected backbone in an ad-hoc network.
An ad-hoc network is a cooperative engagement of a collection of mobile nodes without the required intervention of any centralized access point or existing infrastructure. The lack of a centralized access point or infra structure, although increasing robustness, can create difficulties in optimizing network performrance.
In an ad-hoc network, the concept of an artery node has proven useful for efficient network performance. Some nodes in the ad-hoc network are designated as artery nodes, and the artery nodes are allocated the majority of the bandwidth, or more specifically, they are given the majority of time within a TDMA frame.
With this property, artery nodes provide many desirable features. By possessing the majority of the bandwidth, artery nodes are the natural choices for data routing, and throughput when two nodes wish to communicate across the network. In addition, artery nodes permit the network to quickly respond to traffic bursts, or to throttle traffic as necessary, and thus provide efficient bandwidth and resource allocation.
To ensure these goals are achieved, there are two desired properties for the set of artery nodes. First, for nodes to utilize artery nodes without undue latency, every non-artery node may have at least one neighbor that is an artery node. A neighbor is any node that may be reached without requiring an intermediate node. Having each node with at least one neighbor that is an artery node permits quick response to traffic bursts, and also allows nodes to easily inject their data into the artery node “backbone” for better throughput. Second, to facilitate the use of artery nodes as the data paths of choice, it is desired that the shortest path between any two nodes in the network be along a continuous path of artery nodes.
In a network populated with artery nodes, non-artery node paths of equal or longer length between the nodes may exist, but there may not be any which are shorter. Thus an artery node ad-hoc network is characterized in part by a shortest-path property. Since a path consisting only of artery nodes is required between any two nodes, this implies that the set of artery nodes are connected.
Accordingly, there is a need for a system and method configured to implement an algorithm which, for a given network, chooses a set of artery nodes having the above properties. Yet further, there is a need for such an algorithm that is distributed such that it may be run independently by every node in the network. There is further a need for such an algorithm configured to allow a newly added node to determine if it is to be an artery node. Yet further, although many artery nodes are typically needed to satisfy the shortest-path property, it is desirable that the algorithm be implemented such that only necessary artery nodes be chosen, since they will need to contend with each other for bandwidth.
It would be desirable to provide a system and/or method that provides one or more of these or other advantageous features. Other features and advantages will be made apparent from the present specification. The teachings disclosed extend to those embodiments which fall within the scope of the appended claims, regardless of whether they accomplish one or more of the aforementioned needs.